package io.adrainty.algorithm.mars;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 徒步旅行中的补给问题
 * @link <a href="https://www.marscode.cn/practice/364l85wv6oo6lq?problem_id=7414004855076700204">...</a>
 * @author AdRainty
 * @version V1.0.0
 * @since 2024/11/21 下午9:15
 */
public class Solution002 {

    private Solution002() {}

    public static int solution(int n, int k, int[] data) {
        // Edit your code here
        int cost = 0;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            // 窗口为(left, i]
            int left = Math.max(0, i - k + 1);

            // 维护队列，确保队列中的元素是按照价格从小到大排序的
            while (!deque.isEmpty() && data[deque.peekLast()] > data[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);

            // 如果队列中的最小值已经不在当前窗口内，移除它
            if (!deque.isEmpty() && deque.peekFirst() < left) {
                deque.pollFirst();
            }

            Integer current = deque.peekFirst();
            if (current != null) {
                cost += data[current];
            }
        }

        return cost;
    }

}
